package hash.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * @Description: 有效的数独
 * @Author Stark
 * @Date 2022/3/22 10:22
 **/
public class Num36_IsValidSudoku {
//    Set<Character> set = new HashSet<>();
    public boolean isValidSudoku(char[][] board) {
//        return isValidRow(board) && isValidCol(board) && isVaildArr(board);


//    private boolean isValidRow(char[][] board) {
//        for (int i = 0; i < board.length; i++) {
//            set.clear();
//            for (int j = 0; j < board[i].length; j++) {
//                if(board[i][j] != '.'){
//                    if(!set.add(board[i][j])){
//                        return false;
//                    }
//                }
//            }
//        }
//        return true;
//    }
//
//    private boolean isValidCol(char[][] board) {
//        for (int i = 0; i < board.length; i++) {
//            set.clear();
//            for (int j = 0; j < board[i].length; j++) {
//                if(board[j][i] != '.'){
//                    if(!set.add(board[j][i])){
//                        return false;
//                    }
//                }
//            }
//        }
//        return true;
//    }
//
//    private boolean isVaildArr(char[][] board) {
//        for (int row = 0; row < 3; row++) {
//            for (int col = 0; col < 3; col++) {
//                set.clear();
//                for (int i = 3 * row; i < 3 * (row + 1); i++) {
//                    for (int j = 3 * col; j < 3 * (col + 1); j++) {
//                        if(board[j][i] != '.'){
//                            if(!set.add(board[j][i])){
//                                return false;
//                            }
//                        }
//                    }
//                }
//            }
//        }
//        return true;

        //优化解法
        boolean row[][] = new boolean[9][9];
        boolean col[][] = new boolean[9][9];
        boolean block[][] = new boolean[9][9];
        int index = 0,blockStart = 0;
        for (int i = 0; i < block.length; i++) {
            for (int j = 0; j < block[i].length; j++) {
                if(board[i][j] != '.') {
                    //哈希表的思想
                    index = (int)(board[i][j] - '1');
                    //将数独每个块的元素单独对应到block数组的一行
                    //i是行号,i/3*3,因为block为3行，所以除3取整得到组号，又因为每组block为3个，所以需要乘3
                    //j是列号,j/3,列标再细分出是哪个block（因为block是3列，所以除3取整）
                    blockStart = i / 3 * 3 + j / 3;
                    if(row[i][index] || col[j][index] || block[blockStart][index]){
                        //有一个或多个为true,就返回false,因为初始每个元素都是false
                        //为true的条件就是这个数出现过,并记录在数组里
                        return false;
                    }else{
                        //将出现过的数按哈希记录在boolean数组里
                        row[i][index] = col[j][index] = block[blockStart][index] = true;
                    }
                }
            }
        }
        return true;
    }
}
